package com.sxu.greedy.day3;

import java.util.Arrays;

/**
 * K次取反后的最后化的数组和
 */
public class Test10 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 统计数组中负数的个数
        int m = 0;
        // 统计数组中最小值
        int minElem = Integer.MAX_VALUE;
        int n = nums.length;
        for(int x : nums){
            if(x < 0)
                m++;
            minElem = Math.min(minElem, Math.abs(x));
        }
        // 分类讨论
        int ret = 0;
        if(m >= k){
            Arrays.sort(nums);
            for(int i = 0 ;i<k;i++){
                ret += -nums[i];
            }
            for(int i = k;i<n;i++){
                ret += nums[i];
            }
        } else {
            for(int x : nums){
                ret += Math.abs(x);
            }
            if((k - m) % 2 != 0){
                // 将最小值变为负数 —— 总和减去两次最小值
                ret -= minElem*2;
            }
        }
        return ret;
    }
}
